package graph;

import linearList.LinkedList;
import linearList.Node;
import linearList.SeqList;

public class AdjListGraph<T> {
    // 最大权值，表示无穷大
    public static final int MAX_WEIGHT = 0x0000ffff;

    // 顶点列表
    private SeqList<T> vertexList;

    // 邻接表
    private SeqList<LinkedList<Triple>> adjList;

    /**
     * 带权有向图G4，顺序表，长度=5, 容量=5, 内容如下: (A,B,C,D,E)，邻接表:
     * 0 -> linked list: ((0,1,10), (0,3,30), (0,4,99))
     * 1 -> linked list: ((1,2,50), (1,3,40))
     * 2 -> linked list: ((2,4,10))
     * 3 -> linked list: ((3,2,20), (3,4,60))
     * 4 -> linked list: ()
     * @param args
     */
    public static void main(String args[]) {
        String[] vertices = {"A", "B", "C", "D", "E"};
        Triple edges[] = {new Triple(0,1,10), new Triple(0,3,30), new Triple(0,4,99),
                          new Triple(1,2,50), new Triple(1,3,40),
                          new Triple(2,4,10),
                          new Triple(3,2,20), new Triple(3,4,60),
};
        AdjListGraph<String> graph = new AdjListGraph<String>(vertices, edges);//图7.17
        System.out.println("带权有向图G4，" + graph.toString());
        System.out.println("weight(2,4): " + graph.weight(2,4));
    }

    public AdjListGraph(int length) {
        this.vertexList = new SeqList<>(length);
        this.adjList = new SeqList<LinkedList<Triple>>(length);
    }

    public AdjListGraph(T[] vertices, Triple[] edges) {
        this.vertexList = new SeqList<>(vertices);

        // 初始化邻接表
        this.adjList = new SeqList<LinkedList<Triple>>(vertices.length);
        for (int i = 0; i < vertices.length; i++) {
            this.adjList.insert(new LinkedList<Triple>());
        }

        for (int j = 0; j < edges.length; j++) {
            this.insertEdge(edges[j]);
        }
    }

    public String toString() {
        String str = this.vertexList.toString() + "，邻接表:  \n";
        for (int i = 0; i < this.adjList.size(); i++)
            str += i + " -> " + this.adjList.get(i).toString() + "\n";
        return str;
    }

    // 边
    public void insertEdge(int i, int j, int weight) {
        if (i != j) {
            Triple triple = findTriple(i, j);
            if (triple == null) {
                this.adjList.get(i).insert(new Triple(i, j, weight));
            } else {
                triple.value = weight;
            }
        }
    }

    private Triple findTriple(int i, int j) {
        LinkedList<Triple> row = this.adjList.get(i);
        for (Node<Triple> p = row.head.next; p != null; p = p.next) {
            if (p.data.row == i && p.data.column == j) {
                return p.data;
            }
        }
        return null;
    }

    public void insertEdge(Triple edge) {
        this.insertEdge(edge.row, edge.column, edge.value);
    }

    public void removeEdge(int i, int j) {
        Triple triple = findTriple(i, j);
        if (triple != null) {
            triple.value = MAX_WEIGHT;
        }
    }

    public void removeEdge(Triple edge) {
        this.removeEdge(edge.row, edge.column);
    }

    public int weight(int i, int j) {
        Triple triple = findTriple(i, j);
        return triple == null ? MAX_WEIGHT : triple.value;
    }
}
